package algorithm.leetcode.I401to600;

/**
 * 最长回文子序列,注意不是子串
 * dp[i][j] 从i到j的子序列 (这个子序列一定以s.charAt(i)开头,一定以s.charAt(j)结尾,中间在不在里面无所谓) 中最长的回文子序列长度
 */

//   b b b a b
// b 1 2 3 3 4
// b   1 2 2 3
// b     1 1 3
// a       1 1
// b         1
//
// 横行从下往上,i逆序
// 纵列从左往右,j正序

public class Q516 {

    public int longestPalindromeSubseq(String s) {
        int[][] dp = new int[s.length()][s.length()];
        int maxLength = 0;
        for (int i = s.length()-1; i >= 0; i--) {
            for (int j = i; j < s.length(); j++) {
                if (i == j) dp[i][j] = 1;
                else if (s.charAt(i) == s.charAt(j)) dp[i][j] = dp[i+1][j-1] + 2;
                else dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
                maxLength = Math.max(maxLength, dp[i][j]);
            }
        }
        return dp[0][s.length()-1];
    }

}
